package arithmetic.demo9;

/**
 * 贪心_加油站
 */
class Solution {
    public int canCompleteCircuit(int[] gas, int[] cost) {
        int n = gas.length;
        int[] dp = new int[n]; 
        // 预处理差值
        for(int i = 0; i < n; i++) {
            dp[i] = gas[i] - cost[i];
        }

        int max = -0x3f3f3f3f, index = n-1, sum = 0;
        // 得到起始点
        for(int i = n-1 ; i >= 0; i--) {
            sum += dp[i];
            // 一旦后面一段更大就更新最大起始位置
            if(sum > max) {
                max = sum ;
                index = i;
            }
        }

        // 如果右半段的最大值为负的就已经不成立了
        if(max < 0) {
            return -1;
        }

        // 左半段
        for(int i = 0 ; i < index; i++) {
            max += dp[i];
            if(max < 0) {
                return -1;
            } 
        }

        return index;
    }
}

/**
 * 贪心_加油站
 * 方法二: 检查前面的， 出现不符合的前面数据都舍去
 */

class Solution1 {
    public int canCompleteCircuit(int[] gas, int[] cost) {
        int n = gas.length;

        // 跳跃式加油
        for(int i = 0 ; i < n;) {
            // 开始搜索不成立的条件
            int sum = 0;
            int step = 0;
            for( ; step < n; step++) {
                int j = (i + step) % n;
                sum =  sum + gas[j] - cost[j];
                // 这条路无效
                if(sum < 0) {
                    i = i + step + 1;
                    break;
                }
            }
            // 证明这条路有效
            if(sum >= 0) {
                return i;
            }
        }

        return -1;
    }


}


class  Test {
//    public static void main(String[] args) {
//        Solution1 solution1 = new Solution1();
//        System.out.println(solution1.canCompleteCircuit(new int[]{2,3,4}, new int[]{3,4,3}));
//    }
public static void main(String[] args) {
    Solution2 solution2 = new Solution2();
    System.out.println(solution2.monotoneIncreasingDigits(11));

}
}

/**
 * 题目: 贪心_单调递增的数字
 */


class Solution2 {
    public int monotoneIncreasingDigits(int n) {
        // 预处理
        String str = String.valueOf(n);
        char[] chs = str.toCharArray();
        int len = chs.length;
        // 特殊处理
        if(len == 1) {
            return n;
        }

        // 寻找高位的最大递增位置
        int j = 0;
        while(j + 1 < len && chs[j] <= chs[j + 1]) {
            j++;
        }

        // 如果到了结尾就直接返回 说明当前数字是有效的
        if(j == len -1) {
            return n;
        }

        // 重复的进行回退
        while(j - 1 >= 0 && chs[j - 1] == chs[j]) {
            j--;
        }

        // 修改回退的最后一个位置
        chs[j] = (char)((int)chs[j] - 1);


        // 把后面都修改为9
        for(int i = j+1; i<len; i++){
            chs[i] = '9';
        }

        // 转化回来
        int ret = 0;
        for (int i = 0; i < len; i++) {
            ret = ret * 10 +  (chs[i] - '0');
        }

//        int ret = Integer.valueOf(chs.toString());

        return ret;
    }
}



